//https://leetcode.cn/problems/stickers-to-spell-word/submissions/589248050/
class Solution
{
public:
    vector<string> stickers;
    string target;
    int sn;
    int tn;
    int* memo;

    int dfs(int target_state)
    {
        if (memo[target_state] != -1)
        {
            return memo[target_state];
        }

        int res = tn + 1;
        for (string stick : stickers)
        {
            int need = target_state;
            int cnt[26];
            memset(cnt, 0, sizeof(cnt));

            for (char c : stick)
            {
                cnt[c - 'a']++;
            }
            for (int i = 0; i < tn; i++)
            {
                int ID = target[i] - 'a';
                if (((need >> i) & 1) == 1 && cnt[ID] > 0)
                {
                    cnt[ID]--;
                    need ^= (1 << i);
                }
            }

            if (need < target_state)
            {
                res = min(res, dfs(need) + 1);
            }
        }
        memo[target_state] = res;
        return res;
    }


    int minStickers(vector<string>& stickers, string target)
    {
        this->stickers = stickers;
        this->target = target;
        sn = (int)stickers.size();
        tn = (int)target.size();

        memo = new int[(1 << tn)];
        for (int i = 0; i < (1 << tn); i++)
        {
            memo[i] = -1;
        }
        memo[0] = 0;

        int res = dfs((1 << tn) - 1);
        return (res <= tn ? res : -1);
    }
};
